package 数据结构专栏.面试算法;

/**
 * @Title 二分查找
 * @Author zhengqiang.tan
 * @Date 2021/6/19 4:22 PM
 *
 *
 * 二分查找中中间值的计算：
 * 这是一个经典的话题，如何计算二分查找中的中值？大家一般给出了两种计算方法：
 *
 * 算法一： mid = (low + high) / 2
 * 算法二： mid = low + (high – low)/2
 * 乍看起来，算法一简洁，算法二提取之后，跟算法一没有什么区别。但是实际上，区别是存在的。
 * 算法一的做法，在极端情况下，(low + high)存在着溢出的风险，进而得到错误的mid结果，导致程序错误。
 * 而算法二能够保证计算出来的mid，一定大于low，小于high，不存在溢出的问题。
 *
 */
public class BSearch {

    /**
     * 时间复杂度O(logN)。
     *
     * @param key
     * @param arr
     * @return
     */
    public static int search(int key, int[] arr) {
        int low = 0, high = arr.length - 1;

        while (low < high) {
            int mid = low + (high - low) / 2; // 能够保证计算出来的mid，一定大于low，小于high，不存在溢出的问题
            if (key < arr[mid]) {
                high = mid - 1;
            } else if (key > arr[mid]) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1; // 未找到
    }


    //递归实现：
    public static int search2(int key, int arr[]) {
        return rec(key, arr, 0, arr.length - 1);
    }

    private static int rec(int key, int[] arr, int low, int high) {

        if (low > high) {
            return -1;
        }
        int mid = low + (high - low) / 2;

        if (key < arr[mid]) {
            return rec(key, arr, low, mid - 1);
        } else if (key > arr[mid]) {
            return rec(key, arr, mid + 1, high);
        } else {
            return mid;
        }
    }


}
